package labuladong.leetcode.editor.cn._04dp.ch00;

import java.util.Arrays;

public class _322_CoinChange {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 备忘录
        int[] memo;

        /* 自顶向下递归解法 */
        public int coinChange(int[] coins, int amount) {  // 首选
            memo = new int[amount + 1];
            // dp 数组全都初始化为特殊值
            Arrays.fill(memo, -666);
            return dp(coins, amount);
        }

        int dp(int[] coins, int amount) {
            if (amount == 0) return 0;
            if (amount < 0) return -1;
            // 查备忘录，防止重复计算
            if (memo[amount] != -666)
                return memo[amount];

            int res = Integer.MAX_VALUE;
            for (int coin : coins) {
                // 计算子问题的结果
                int subProblem = dp(coins, amount - coin);
                // 子问题无解则跳过
                if (subProblem == -1) continue;
                // 在子问题中选择最优解，然后加一
                res = Math.min(res, subProblem + 1);
            }
            // 把计算结果存入备忘录
            memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
            return memo[amount];
        }

        /* dp 数组的迭代解法*/
        public int coinChange2(int[] coins, int amount) {
            int[] dp = new int[amount + 1];
            // 数组大小为 amount + 1，初始值也为 amount + 1
            Arrays.fill(dp, amount + 1);

            // base case
            dp[0] = 0;
            // 外层 for 循环在遍历所有状态的所有取值
            for (int i = 0; i < dp.length; i++) {
                // 内层 for 循环在求所有选择的最小值
                for (int coin : coins) {
                    // 子问题无解，跳过
                    if (i - coin < 0) {
                        continue;
                    }
                    // 状态转移
                    dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
                }
            }
            // 看看金额 amount 能不能凑出来
            return (dp[amount] == amount + 1) ? -1 : dp[amount];
        }

        /* 暴力递归解法 */
        public int coinChange3(int[] coins, int amount) {
            // base case
            if (amount == 0) return 0;
            if (amount < 0) return -1;

            int res = Integer.MAX_VALUE;
            for (int coin : coins) {
                // 计算子问题的结果
                int subProblem = coinChange3(coins, amount - coin);
                // 子问题无解则跳过
                if (subProblem == -1) continue;
                // 在子问题中选择最优解, 然后加一
                res = Math.min(res, subProblem + 1);
            }
            return res == Integer.MAX_VALUE ? -1 : res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new _322_CoinChange().new Solution();
        int[] coins = {1, 2, 5};
        System.out.println(solution.coinChange(coins, 4));
        System.out.println(solution.coinChange2(coins, 4));
        System.out.println(solution.coinChange3(coins, 4));
    }
}
